//题目:
// 给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
// 差值是一个正数，其数值等于两值之差的绝对值。
#include<iostream>
#include<limits.h>

using namespace std;
//代码:
struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution 
{
public:
    // void Mid_Order(TreeNode* root,vector<int>& v)
    // {
    //     if(root==nullptr)return;
    //     //左子树
    //     Mid_Order(root->left,v);
    //     //根
    //     v.push_back(root->val);
    //     //右子树
    //     Mid_Order(root->right,v);
    // }
    // int getMinimumDifference(TreeNode* root) 
    // {
    //     //二叉搜索树，中序遍历，升序，判断两两相邻元素的差值
    //     vector<int> v;//升序排序
    //     Mid_Order(root,v);
    //     int ret=INT_MAX;
    //     for(int i=0;i<v.size()-1;i++)
    //     {
    //         ret=min(ret,abs(v[i]-v[i+1]));
    //     }
    //     return ret;
    // }
    void Mid_Order(TreeNode* root,int& prev,int& ret,bool& flag)
    {
        if(root==nullptr)return;
        //左子树
        Mid_Order(root->left,prev,ret,flag);
        //根:此时，prev是上一个结点的值，val是本节点的值
        if(flag==false)
        {
            prev=root->val;
            flag=true;
        }
        else
        {
            ret=min(ret,root->val-prev);
            prev=root->val;//更新prev
        }
        //右子树
        Mid_Order(root->right,prev,ret,flag);
    }
    int getMinimumDifference(TreeNode* root) 
    {
        //二叉搜索树，中序遍历，升序，判断两两相邻元素的差值
        // vector<int> v;//升序排序
        int prev,ret=INT_MAX;
        bool flag=false;
        Mid_Order(root,prev,ret,flag);
        // int ret=INT_MAX;
        // for(int i=0;i<v.size()-1;i++)
        // {
        //     ret=min(ret,abs(v[i]-v[i+1]));
        // }
        return ret;
    }
};